lib/Mi manual de algoritmos/version_world_finals_2009/src/grafos/dijkstra.cpp

   1 // //Complejidad: O(E log V)
   2 // ¡Si hay ciclos de peso negativo, el algoritmo se queda
   3 // en un ciclo infinito!
   4 // Usar Bellman-Ford en ese caso.
   5 struct edge{
   6   int to, weight;
   7   edge() {}
   8   edge(int t, int w) : to(t), weight(w) {}
   9   bool operator < (const edge &that) const {
  10     return weight > that.weight;
  11   }
  12 };
  13
  14 vector<edge> g[MAXNODES];
  15 // g[i] es la lista de aristas salientes del nodo i.  Cada una
  16 // indica hacia que nodo va (to) y su peso (weight).  Para
  17 // aristas bidireccionales se deben crear 2 aristas dirigidas.
  18
  19 // encuentra el camino más corto entre s y todos los demás
  20 // nodos.
  21 int d[MAXNODES]; //d[i] = distancia más corta desde s hasta i
  22 int p[MAXNODES]; //p[i] = predecesor de i en la ruta más corta
  23 int dijkstra(int s, int n){
  24   //s = nodo inicial, n = número de nodos
  25   for (int i=0; i<n; ++i){
  26     d[i] = INT_MAX;
  27     p[i] = -1;
  28   }
  29   d[s] = 0;
  30   priority_queue<edge> q;
  31   q.push(edge(s, 0));
  32   while (!q.empty()){
  33     int node = q.top().to;
  34     int dist = q.top().weight;
  35     q.pop();
  36
  37     if (dist > d[node]) continue;
  38     if (node == t){
  39       //dist es la distancia más corta hasta t.
  40       //Para reconstruir la ruta se pueden seguir
  41       //los p[i] hasta que sea -1.
  42       return dist;
  43     }
  44
  45     for (int i=0; i<g[node].size(); ++i){
  46       int to = g[node][i].to;
  47       int w_extra = g[node][i].weight;
  48
  49       if (dist + w_extra < d[to]){
  50         d[to] = dist + w_extra;
  51         p[to] = node;
  52         q.push(edge(to, d[to]));
  53       }
  54     }
  55   }
  56   return INT_MAX;
  57 }